package com.sun.test;

public class Fibonacci {
    public static void main(String[] args) {
        /*
         * 16.斐波那契数列
         * 斐波那契数列，又称黄金分割数列，
         * 指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，
         * 斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
         * */
        /*
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入要打印的斐波那契数列的个数");
		int count = sc.nextInt();
		int x = 1;
		int y = 1;
		int z = 0;
		//前两位是1
		for(int i = 1;i<=count;i++){
			if(i==1 || i==2){
				System.out.print(1+"\t");
			}else{
				z=x+y;
				x=y;
				y=z;
				System.out.print(z+"\t");
			}
		}
		*/
        //System.out.println(getFib3(10));
       /* for(int i = 1;i<=10;i++){
            System.out.print(getNumber(i)+"\t");
        }*/


    }

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式，基于递归实现
     * @param n
     * @return
     */
    public static int getFib(int n){
        if(n<0){
            return -1;
        }else if(n==0){
            return 0;
        }else if(n==1||n==2){
            return 1;
        }else {
            return getFib(n-1)+getFib(n-2);
        }
    }

    /**
     * 方式2：
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式，基于变量实现
     * @param n
     * @return
     */
    public static int getFib2(int n){
        if(n<0){
            return -1;
        }else if (n == 0) {
            return 0;
        }else if (n == 1||n==2) {
            return 1;
        }else{
            int a=1,b=1,c=0;
            for (int i = 3; i <=n; i++) {
                c=a+b;
                a=b;
                b=c;
            }
            return c;
        }
    }

    /**
     * 返回斐波那契数第n个值,n从0开始
     * 实现方式：基于数组实现
     * @param n
     * @return
     */
    public static int getFib3(int n){
        if(n<0){
            return -1;
        }else if (n == 0) {
            return 0;
        }else if(n==1||n==2){
            return 1;
        }else {
            int[] fibArray=new int[n+1];
            fibArray[0]=0;
            fibArray[1]=fibArray[2]=1;
            for (int i = 3; i <=n ; i++) {
                fibArray[i]=fibArray[i-1]+fibArray[i-2];
            }
            return fibArray[n];
        }
    }

    /**
     * 递归函数:
     *         在程序运行过程中，有时需要调用程序本身，此时可以使用递归
     *         注意：在程序中，能不使用递归就不要使用递归，使用递归的时候会加大资源的消耗
     *         如果递归的层次比较深，会造成栈溢出，如果不使用递归无法解决问题的话，就必须要使用递归
     *         比如：输出某个磁盘目录下的所有文件名称
     * @param number
     * @return
     */
    public static int getNumber(int number){
        if(number==1||number==2){
            return 1;
        }else {
            return getNumber(number - 1)+getNumber(number-2);
        }
    }
}

